#include "sort.h"

#define N 200000
int nums[N];

bool isRight(int* a, int n)
{
	bool flag = true;
	for (int i = 1; i < n; i++)
	{
		if (a[i - 1] > a[i])
		{
			flag = false;
			break;
		}
	}
	return flag;
}

void creat()
{
	for (int i = 0; i < N; i++)
	{
		nums[i] = rand();
	}
}

void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

void InsertTest()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = nums[i];
	}
	size_t t1 = clock();
	InsertSort(a, N);
	size_t t2 = clock();

	//Print(a, N);
	printf("%zu\n", t2 - t1);
	//printf("%d\n", isRight(a, N));
}

void ShellSortTest()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = nums[i];
	}
	size_t t1 = clock();
	ShellSort(a, N);
	size_t t2 = clock();

	//Print(a, N);
	printf("%zu\n", t2 - t1);
	//printf("%d\n", isRight(a, N));
}

void BubbleSortTest()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = nums[i];
	}
	size_t t1 = clock();
	BubbleSort(a, N);
	size_t t2 = clock();
	
	Print(a, N);
	//printf("%zu\n", t2 - t1);
	printf("%d\n", isRight(a, N));
}

void SelectSortTest()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = nums[i];
	}
	size_t t1 = clock();
	SelectSort(a, N);
	size_t t2 = clock();

	//Print(a, N);
	//printf("%zu\n", t2 - t1);
	printf("%d\n", isRight(a, N));
}

void HeapSortTest()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = nums[i];
	}
	size_t t1 = clock();
	HeapSort(a, N);
	size_t t2 = clock();

	//Print(a, N);
	//printf("%zu\n", t2 - t1);
	printf("%d\n", isRight(a, N));
}

void MergeSortTest()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = nums[i];
	}
	size_t t1 = clock();
	MergeSort(a, 0, N - 1);
	size_t t2 = clock();

	Print(a, N);
	//printf("%zu\n", t2 - t1);
	printf("\n%d\n", isRight(a, N));
}

void MergeSortNonRtTest()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = nums[i];
	}
	size_t t1 = clock();
	MergeSortNonR(a, 0, N - 1);
	size_t t2 = clock();

	Print(a, N);
	printf("%zu\n", t2 - t1);
	printf("\n%d\n", isRight(a, N));
}

void QuickSortTest()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = nums[i];
	}
	size_t t1 = clock();
	QuickSort(a, 0, N - 1);
	size_t t2 = clock();

	//Print(a, N);
	printf("%zu\n", t2 - t1);
	printf("\n%d\n", isRight(a, N));
}

void PartSort2Test()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = nums[i];
	}
	size_t t1 = clock();
	PartSort2(a, 0, N - 1);
	size_t t2 = clock();

	//Print(a, N);
	printf("%zu\n", t2 - t1);
	printf("\n%d\n", isRight(a, N));
}

void PartSort3Test()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = nums[i];
	}
	size_t t1 = clock();
	PartSort3(a, 0, N - 1);
	size_t t2 = clock();

	//Print(a, N);
	printf("%zu\n", t2 - t1);
	printf("\n%d\n", isRight(a, N));
}

void QuickSortNonRTest()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = nums[i];
	}
	size_t t1 = clock();
	QuickSortNonR(a, 0, N - 1);
	size_t t2 = clock();

	//Print(a, N);
	printf("%zu\n", t2 - t1);
	printf("\n%d\n", isRight(a, N));
}

int main()
{
	srand((unsigned)time(NULL));
	creat();
	//printf("%d\n", isRight(nums, N));
	//InsertTest();
	//ShellSortTest();
	//BubbleSortTest();
	//SelectSortTest();
	//HeapSortTest();
	//MergeSortNonRtTest();
	//QuickSortTest();
	//PartSort2Test();
	//PartSort3Test();
	//QuickSortNonRTest();
	int sum = 0;
	for (int i = 99; i >= 1; i--)
		sum += i;
	printf("%d", sum);
	return 0;
}